package algorithm.tree;

import java.util.Arrays;

/**
 * <p>
 * 红黑树
 * 红黑树（Red Black Tree） 是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，
 * 1. 红黑树五大特性
 * 所有节点非红即黑
 * 根节点是黑色
 * 页节点是黑色
 * 不能有连续的红色
 * 任意节点到叶子节点路径中有相同数量的黑色节点
 * 2. 变色
 * 如果当前节点的父亲节点和叔叔节点均是红色，那么执行以下变色操作：
 * 3. 左旋
 * 条件：
 * 父亲是红色
 * 叔叔是黑色
 * 当前是右子树
 * 执行：
 * 已父亲进行旋转
 * 4. 右旋
 * 条件：
 * 父亲是红色
 * 叔叔是黑色
 * 当前是左子树
 * <p>
 * 执行：
 * 父亲节点 变为 黑色
 * 爷爷节点变为红色
 * 再已爷爷节点进行旋转
 * </p>
 *
 * @author liyi
 * @since 2024/4/18 13:59
 */
public class RedBlackTree {

    private final int R = 0;
    private final int B = 1;

    private class Node {

        int key = -1;
        int color = B; // 默认黑
        Node left = nil; // nil表示空
        Node right = nil;
        Node p = nil;

        Node(int key) {
            this.key = key;
        }

        @Override
        public String toString() {
            return "Node [key=" + key + ", color=" + color + ", left=" + left.key + ", right=" + right.key + ", p="
                    + p.key + "]" + "\r\n";
        }

    }

    private final Node nil = new Node(-1);
    private Node root = nil;

    public void printTree(Node node) {
        if (node == nil) {
            return;
        }
        printTree(node.left);
        System.out.print(node.toString());
        printTree(node.right);
    }

    private void insert(Node node) {
        Node temp = root;
        if (root == nil) {
            root = node;
            node.color = B;
            node.p = nil;
        } else {
            node.color = R;
            while (true) {
                if (node.key < temp.key) {
                    if (temp.left == nil) {
                        temp.left = node;
                        node.p = temp;
                        break;
                    } else {
                        temp = temp.left;
                    }
                } else if (node.key >= temp.key) {
                    if (temp.right == nil) {
                        temp.right = node;
                        node.p = temp;
                        break;
                    } else {
                        temp = temp.right;
                    }
                }
            }
            fixTree(node);
        }
    }

    /**
     * 修正树
     *
     * @param node
     */
    private void fixTree(Node node) {
        while (node.p.color == R) {//1当前节点的父亲节点是红色一定要处理(因为插入的当前节点默认就是红色)
            Node y = nil;//叔叔节点
            if (node.p == node.p.p.left) {//当前节点的父节点是左树
                y = node.p.p.right;

                if (y != nil && y.color == R) {//2 且叔叔节点也是红色
                    //变色 (父节点和叔叔节点变色,爷爷变红)
                    node.p.color = B;
                    y.color = B;
                    node.p.p.color = R;
                    node = node.p.p;//这里用于下一次循环(向上递归)
                    continue;
                }
                if (node == node.p.right) {
                    node = node.p;//父节点作为当前节点，准备左旋
                    rotateLeft(node);
                }
                node.p.color = B;
                node.p.p.color = R;
                rotateRight(node.p.p);
            } else {//当前节点的父节点是右树
                y = node.p.p.left;
                if (y != nil && y.color == R) {
                    node.p.color = B;
                    y.color = B;
                    node.p.p.color = R;
                    node = node.p.p;
                    continue;
                }
                if (node == node.p.left) {
                    node = node.p;
                    rotateRight(node);
                }
                node.p.color = B;
                node.p.p.color = R;
                rotateLeft(node.p.p);
            }
        }
        root.color = B;
    }

    /**
     * 左旋不变色
     * 条件：父亲是红色，叔叔是黑色，当前是右子树
     * 执行：已父亲进行旋转
     *
     * @param node
     */
    void rotateLeft(Node node) {
        if (node.p != nil) {
            if (node == node.p.left) {
                node.p.left = node.right;
            } else {
                node.p.right = node.right;
            }
            node.right.p = node.p;
            node.p = node.right;
            if (node.right.left != nil) {
                node.right.left.p = node;
            }
            node.right = node.right.left;
            node.p.left = node;
        } else {
            Node right = root.right;
            root.right = right.left;
            right.left.p = root;
            root.p = right;
            right.left = root;
            right.p = nil;
            root = right;
        }
    }

    /**
     * 右旋要先白色 （父亲节点 变为 黑色）
     * 条件：父亲是红色，叔叔是黑色，当前是左子树
     * 执行：爷爷节点进行旋转
     *
     * @param node
     */
    void rotateRight(Node node) {
        if (node.p != nil) {
            if (node == node.p.left) {
                node.p.left = node.left;
            } else {
                node.p.right = node.left;
            }

            node.left.p = node.p;
            node.p = node.left;
            if (node.left.right != nil) {
                node.left.right.p = node;
            }
            node.left = node.left.right;
            node.p.right = node;
        } else {
            Node left = root.left;
            root.left = root.left.right;
            left.right.p = root;
            root.p = left;
            left.right = root;
            left.p = nil;
            root = left;
        }
    }

    public void creatTree() {
        int data[] = {23, 32, 15, 221, 3};
        Node node;
        System.out.println(Arrays.toString(data));
        for (int i = 0; i < data.length; i++) {
            node = new Node(data[i]);
            insert(node);
        }
        printTree(root);
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        RedBlackTree bst = new RedBlackTree();
        bst.creatTree();
    }
}
